#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <pthread.h>
#define SIZE 80

struct total{ 
  int *tableau;
  int taille;
};

struct total *create_total(int *tab, int size){

  struct total *tmp = malloc(sizeof(struct total));
  tmp->tableau = tab;
  tmp->taille = size;
  return tmp;
}

// classement ascendant
void *thread_tri(struct total *total){

  int i, *tab = total->tableau;
  int taille = total->taille;

  // cas taille = 1 ou 2. Dans le premier cas on renvoie direct
  // le tableau, dans le deuxième on échange si besoin les valeurs
  if (taille == 1){
    pthread_exit(NULL);
  }
  else {
    if (taille == 2){
      if (tab[0] >= tab[1]){
	int tmp = tab[0];
	tab[0] = tab[1];
	tab[1] = tmp;
      }
      pthread_exit(NULL);     
    }
    // cas où la taille du tableau est > 2
    else {
      int pivot = tab[taille/2];
      int place_pivot;
      int tmp_tab[taille];
      int queue = taille-1;
      int tete = 0;
      int pivots = 0;
      
      // on tri le tableau par rappor au pivot
      // choisi arbitrairement au milieu.
      for (i = 0; i < taille; i++){
	if (tab[i] < pivot){
	  tmp_tab[tete++] = tab[i];
	}
	else {
	  if (tab[i] == pivot){
	    pivots++;
	  }
	  else {
	    tmp_tab[queue--] = tab[i];
	  }
	}
      }
      // on remplit les valeurs = au pivot à la toute
      // toute fin sinon ça va pas marcher..
      for (i=0; i<pivots; i++){
	tmp_tab[queue--] = pivot;
      }

      // on conserve la place du pivot dans le nouveau tableau
      // (puisque c'est cette place qui permet de séparer
      //  le tableau en deux à envoyer au threads)
      place_pivot = queue+1;
      if (place_pivot == 0){
	place_pivot++;
      }
      
      for (i = 0; i < taille; i++){
	tab[i] = tmp_tab[i];
      }
      
      int *r_tab, *l_tab;
      if (place_pivot > 1){
	l_tab = malloc(place_pivot*sizeof(int));
	for (i = 0; i < place_pivot; i++){
	  l_tab[i] = tmp_tab[i];
	}
      }
      if ((taille-place_pivot) > 2){
	r_tab = malloc((taille-place_pivot)*sizeof(int));
	for (i = 0; i < (taille-place_pivot); i++){
	  r_tab[i] = tmp_tab[(taille-i-1)];
	}
      }
      
      // ce tableau ne contient pas le pivot, donc dès que sa taille
      // dépasse 1, il n'est pas trié dans le cas général.
      if (place_pivot > 1){
	pthread_t thread1;
	struct total *l_total = create_total(l_tab, place_pivot);
	pthread_create(&thread1, NULL, thread_tri, l_total);
	pthread_join(thread1, NULL);
	
	for (i=0; i<place_pivot; i++){
	  tab[i] = l_tab[i];
	}

	free(l_tab);
	free(l_total);
      }

      // de ce côté, le tableau contient le pivot, donc si
      // la taille est <= 2, le tableau est bien trié.
      if ( (taille-place_pivot) > 2){
	pthread_t thread2;
	struct total *r_total = create_total(r_tab, taille-place_pivot);
	pthread_create(&thread2, NULL, thread_tri, r_total);
	pthread_join(thread2, NULL);
	
	for (i=0; i<(taille-place_pivot); i++){
	  tab[place_pivot + i] = r_tab[i];
	}
	free(r_tab);
	free(r_total);
	}      
      pthread_exit(NULL);
    }
  }
  return NULL;
}

int main(){

  srand(time(NULL));

  int i;

  printf("Avant :\n*****\n");
  int *tab = malloc(SIZE*sizeof(int));
  for (i=0; i<SIZE; i++){
    tab[i] = rand()%20;
    printf("%d ", tab[i]);
  }
  printf("\n*****\n");

  struct total *total = malloc(sizeof(struct total));
  total->tableau = tab;
  total->taille = SIZE;

  pthread_t thread;
  pthread_create(&thread, NULL, thread_tri, total);
  pthread_join(thread, NULL);

  printf("Après :\n*****\n");
  for (i=0; i<SIZE; i++){
    printf("%d ", tab[i]);
  }
  printf("\n*****\n\n");

  free(tab);
  free(total);

  return EXIT_SUCCESS;

}
